<!-- 分治法-快速排序 -->
<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
    <title>分治之快速排序</title>
    <script type="text/javascript" src="USE.js"></script>
	<script>
        var a=[];
		function swap(a,i,j)     //交换函数
	{                  
		var temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	function partition(a,p,q)    //对数组进行分区 快速排序主要程序
	{
		var x=a[p];              
		var i=p,j;
		for(j=p+1;j<=q;j++)
		{
			if(a[j]<=x)          //左小右大  若要左大右小 改为>=
			{
				i++;             //i从p开始的,而且i交换后再遇到就要前进 
				swap(a,i,j);     //交换
			}
		}
		swap(a,p,i);             //关键点：将x放入正确的位置
        $("#sort").append("开始位置："+p+"; 终止位置："+q+"基准："+x+"; 基准所在位置："+i+"; 数组："+a+"<br/>");  ////输出 基准及其相关数据  便于检查程序运行是否正确，调用了jq库
		return i;
	}
	function quicksort(a,p,q)     //递归的调用     
	{
		if(p<q)                   //执行条件
		{   
            var r=partition(a,p,q);
            
			quicksort(a,p,r-1);
			quicksort(a,r+1,q);
		}  
	}	
	function  quicksort1()
	{   document.getElementById("sort").innerHTML="";               //每次执行前清空
		a=document.getElementById("arr1").value.split(",");         //将文本框输入的数组转换为字符类型数组
		for(var i=0;i<a.length;i++)                                 //进行排序需要把字符类型数组转换为整型数组
			a[i]=parseInt(a[i]);
		   quicksort(a,0,a.length-1);
           $("#sort").append("最终结果："+a);                        //输出
	}
	</script>
	
	<style>
		body
		{
			background-color: rgb(255, 255, 255);
			margin: 0;
			text-align:center

		}
		.d1
		{
			border:1px solid rgb(0, 0, 0);
			width:500px;
			height:500px;
			margin:0 auto;
			text-align:left;
			padding-left:50;
			
		}
		#sort /*结果*/
		{   
			color: rgb(0, 0, 0);
		}
	</style>
</head>
<body >
	输入数组（注意数字用英文逗号隔开）：
	<h1>  </h1>
  <input type="text" name="arr1" id="arr1" style="width:400px" value=""/>
    <h2>  </h2>
	<br/>
    <input type="button" value="分治快排" onclick="quicksort1()" style="width: 150px;"/>
	<br/>
	<h3>  </h3>
	输出排序后：
	<div class="d1" id="sort"style ="width:800px">
	</div>
</body>
</html>